# 28 找出字符串种第一个匹配项的下标
# https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/
# Date: 2025/3/26
from leetcode import test_function


def strStr(haystack: str, needle: str) -> int:
    """KMP字符串匹配算法
    KMP 方法算法就利用之前判断过的信息，通过一个 next 数组，保存模式串中前后最长公共子序列的长度
    每次回溯时，通过 next 数组找到，前面匹配过的位置，省去了大量的计算时间。
    例如: haystack = "aabaabaaf", needle = "aabaaf"
    在匹配到needle种的"f"时发现不匹配, 那么最长公共子序列为"aab", 所以从haystack的第3个字符开始重新匹配就可以了
    """
    def build_next_array(pattern):
        next_array = [0] * len(pattern)
        j = 0  # 前缀指针
        for i in range(1, len(pattern)):
            # 当字符不匹配时，回退j到next_array[j-1]
            while j > 0 and pattern[i] != pattern[j]:
                j = next_array[j - 1]
            if pattern[i] == pattern[j]:
                j += 1
            next_array[i] = j
        return next_array

    # 如果模式串为空，返回0（根据题目要求处理）
    if not needle:
        return 0
    # 生成部分匹配表（next数组）
    next_array = build_next_array(needle)
    i = 0  # 主串指针
    j = 0  # 模式串指针
    while i < len(haystack):
        if haystack[i] == needle[j]:
            i += 1
            j += 1
            # 匹配成功，返回起始索引
            if j == len(needle):
                return i - j
        else:
            if j > 0:
                # 根据next数组回退模式串指针
                j = next_array[j - 1]
            else:
                i += 1
    # 未找到匹配
    return -1


if __name__ == '__main__':
    inp = [{"haystack": "sadbutsad", "needle": "sad"},
           {"haystack": "aabaabaaf", "needle": "aabaaf"},
           {"haystack": "leetcode", "needle": "leeto"},
           {"haystack": "aaaaaaacaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaa"
                        "aaaaaacaaaaaaaaaabc", "needle": "aaaaabc"},
           ]
    out = [0, 3, -1, 106]
    test_function(strStr, inp, out)